#include <algorithm>
#include <vector>

using std::vector;

static void backtrace(vector<int>& select, vector<int>& trace, vector<vector<int>>& res)
{
    if (select.size() == trace.size()) {
        auto tmp{ vector<int>(trace.begin(), trace.end()) };
        res.push_back(tmp);
    }
    else {
        for (auto i : select) {
            if (std::find(trace.begin(), trace.end(), i) != trace.end()) {
                continue;
            }
            else {
                trace.push_back(i);
                backtrace(select, trace, res);
                trace.pop_back();
            }
        }
    }
}

vector<vector<int>> Permute(vector<int>& nums)
{
    vector<vector<int>> res{};
    if (nums.size() > 0U) {
        vector<int> trace{};
        backtrace(nums, trace, res);
    }
    return res;
}